package zhengqc.sort;

public class BubbleSort<E extends Comparable<E>> extends Sort<E> {
    public BubbleSort() {
        this.sortName = "BubbleSort";
    }
    private static <E> void swap(E[] array, int i, int j) {
        E t = array[i];
        array[i] = array[j];
        array[j] = t;
    }
    @Override
    public void sort(E[] array) {
        for (int i = 0; i+1 < array.length; ) {
            // 第 i 轮开始, array[n-i, n) 已经排好序
            // 第 i 轮, 通过冒泡在 array[n-i-1] 位置放上合适的元素
            int lastSwappedIndex = 0;
            for (int j = 0; j < array.length-i-1; ++j) {
                if ( array[j].compareTo(array[j+1]) > 0 ) {
                    swap(array, j, j+1);
                    lastSwappedIndex = j + 1;
                }
            }

            i = array.length - lastSwappedIndex;
            // 第 i 轮结束, array[n-i-1, n) 已经排好序
        }
    }


//    @Override // Version 2
//    public void sort(E[] array) {
//        for (int i = 0; i+1 < array.length; ++i) {
//            // 第 i 轮开始, array[n-i, n) 已经排好序
//            // 第 i 轮, 通过冒泡在 array[n-i-1] 位置放上合适的元素
//            boolean isSwapped = false;
//            for (int j = 0; j < array.length-i-1; ++j) {
//                if ( array[j].compareTo(array[j+1]) > 0 ) {
//                    swap(array, j, j+1);
//                    isSwapped = true;
//                }
//            }
//            if ( !isSwapped ) break;
//            // 第 i 轮结束, array[n-i-1, n) 已经排好序
//        }
//    }

//    @Override // Version 1
//    public void sort(E[] array) {
//        for (int i = 0; i+1 < array.length; ++i) {
//            // 第 i 轮开始, array[n-i, n) 已经排好序
//            // 第 i 轮, 通过冒泡在 array[n-i-1] 位置放上合适的元素
//            for (int j = 0; j < array.length-i-1; ++j) {
//                if ( array[j].compareTo(array[j+1]) > 0 ) {
//                    swap(array, j, j+1);
//                }
//            }
//            // 第 i 轮结束, array[n-i-1, n) 已经排好序
//        }
//    }
}
